package com.yuxi.al.leercode;

import java.io.Serializable;

/**
 * 两个链表合并，节点元素满10做一次进位
 * Created by yuxi on 2017/3/26.
 */
public class LinkedAdd {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        ListNode listNode2 = new ListNode(5, new ListNode(88,null));
        ListNode result = addTwoNumbers(listNode1, listNode2);
        while (result != null) {
            System.out.print(result.val+"---->");
            result = result.next;
        }
    }

    /******************************/
    /* 突然想到之前有一次面试的时候被人问到一个问题，如何计算两个超大的数之和，
    那个时候真的一筹莫展，现在想想链表合并的变种就不是能解决这个问题嘛，把两个超大数转化为字符串，
    然后每一个字符串相加，进位也考虑到了，这个字符串应该是逆序的！！！！！！*/
    /******************************/


    /**
     * leetcode 上面的大神脑子里面真的不知道装的什么，这样的方法都可以想的出来，真他妈的是服了！！！！！
     * 两个链表合并，需要注意的是 如果链表的节点相加和等于10就做一次进位，移到下一个节点
     *
     * @param listNode1 链表1
     * @param listNode2 链表2
     * @return
     */
    private static ListNode addTwoNumbers(ListNode listNode1, ListNode listNode2) {
        ListNode l1 = listNode1;
        ListNode l2 = listNode2;
        ListNode l3 = new ListNode(0, null);
        ListNode tempListNode = l3;
        int sum = 0;
        while (l1 != null || l2 != null) {
            // 为了满10做进位运算
            sum /= 10;
            //每个链表节点求和，节点后移
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            //赋值给新建的链表，注意要做取模运算
            tempListNode.next = new ListNode(sum % 10, null);
            tempListNode = tempListNode.next;
        }
        //防止最后一个节点是需要进位的节点
        if (sum /10!= 0) {
            tempListNode.next = new ListNode(1, null);
        }
        //从下一个节点开始返回，因为第一个节点是0
        return l3.next;
    }

    /**
     * 创建链表过程
     */
    static class ListNode  implements Serializable{

        public int val;
        public ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
